package org.skywork.top.core.algorithm.str;

import java.util.*;
import java.util.concurrent.atomic.AtomicBoolean;

/**
 * 有效的括号
 */
public class no_20 {

    /**
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     *
     * 有效字符串需满足：
     *
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     */
    public boolean isValid(String s) {

        /**
         * 示例 1：
         *
         * 输入：s = "()"
         *
         * 输出：true
         *
         * 示例 2：
         *
         * 输入：s = "()[]{}"
         *
         * 输出：true
         *
         * 示例 3：
         *
         * 输入：s = "(]"
         *
         * 输出：false
         *
         * 示例 4：
         *
         * 输入：s = "([])"
         *
         * 输出：true
         */
        String[] strs = s.split("");
        if (strs.length % 2 != 0) {
            return false;
        }
        Stack<String> left = new Stack<>();
        Stack<String> right = new Stack<>();
        for (String str : strs){
            if (str.equals("(") || str.equals("{") || str.equals("[")){
                left.push(str);
            }

            if(str.equals(")") || str.equals("}") || str.equals("]")){
                right.push(str);
            }
        }

        if(left.size() != right.size()){
            return false;
        }

        Map<String, String> map = new HashMap<>();
        map.put("(", ")");
        map.put("[", "]");
        map.put("{", "}");

        while (!left.isEmpty() && !right.isEmpty()){
            String leftStr = left.pop();

            String s1 = map.get(leftStr);
            int index = right.indexOf(s1);
            if (index == -1){
                return false;
            }else{
                right.remove(index);
            }
        }
        return true;
    }


    public static boolean isValid2(String s) {
        Map<String, String> map = new HashMap<>();
        map.put("(", ")");
        map.put("[", "]");
        map.put("{", "}");
        String[] strs = s.split("");
        if(s.length() > 0 && !map.containsKey(strs[0])) return false;

        Stack<String> stack = new Stack<String>();
        for(String c : strs){
            if(map.containsKey(c)) {
                stack.push(c);
            }else{
                if(stack.isEmpty()){
                    return false;
                }
                if(!map.get(stack.pop()).equals(c)){
                    return false;
                }
            }
        }
        return stack.size() == 0;
    }


    public static void main(String[] args) {
        String s = "(){}}{";
        boolean flag = isValid2(s);
        System.out.println(flag);
    }
}
